package com.cg.offer;

import org.junit.Test;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * 剑指Offer 62.圆圈中最后剩下的数字
 *
 * @program: LeetCode->Offer_62
 * @description: 剑指Offer 62.圆圈中最后剩下的数字
 * @author: cg
 * @create: 2022-04-01 15:48
 **/
public class Offer_62 {

    @Test
    public void test62() {
        System.out.println(lastRemaining(10, 17));
    }

    /**
     * 0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
     * <p>
     * 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
     * <p>
     * 示例 1：
     * 输入: n = 5, m = 3
     * 输出: 3
     * <p>
     * 示例 2：
     * 输入: n = 10, m = 17
     * 输出: 2
     * <p>
     * 限制：
     * 1 <= n <= 10^5
     * 1 <= m <= 10^6
     *
     * @param n
     * @param m
     * @return
     */
    public int lastRemaining(int n, int m) {
        /*// 我着小脑袋能想到的，但超时了
        List<Integer> list = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int index = 0;
        while (list.size() > 1) {
            index = (index + m - 1) % n;
            list.remove(index);
            n--;
        }
        return list.get(0);*/
        /*
       思路：使用数学方法(先举例)
               你要知道最后的结果是3，带着结果去看问题

           第一次，【0, 1, 2, 3, 4】，本轮要踢出2                                  看3
           (下一轮开始从3计数，为了方便读者看出规律，将开始计数的那一位移到开头)
           第二次，【3, 4, 0, 1】，本轮要踢出0                                     看1
           第三次，【1, 3, 4】，本轮要踢出4                                        看1
           第四次，【1, 3】 本轮要踢出1                                            看3
           第五次，【3】
           最后返回3

           我们要使用的数学方法，就是从结果0号位置，反推最开始在哪
           你从第二次，向上看第一次
           你会发现，原来3在0的位置
                   现在，3在(0 + 3) % 5
                           => +3 回到上次的位置
                           => %5 防止数组溢出，并且数组本来就是循环数组

           f(n) = ( f(n - 1) + m ) % n
           解释意思：
               f(n) 表示上一次
               f(n - 1) 表示这次，因为我们要从这次回推上一次
               m 表示隔几个
               n表示上一次的数组长度

        */
        // 最后只剩下一位，坐标肯定是0
        int res = 0;
        for (int i = 2; i <= n; i++) {
            res = (res + m) % i;
        }
        return res;
    }

}
